package com.algorithm.liyc.echa;

import com.algorithm.liyc.entity.TreeNode;

import java.util.Stack;

/**
 * 0098.验证二叉搜索树
 *
 * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
 * 假设一个二叉搜索树具有如下特征：
 * ● 节点的左子树只包含小于当前节点的数。
 * ● 节点的右子树只包含大于当前节点的数。
 * ● 所有左子树和右子树自身必须也是二叉搜索树。
 *
 * 要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。注意二叉搜索树中不能有重复元素。
 * 有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。
 *
 * 这道题目比较容易陷入两个陷阱：
 * 陷阱1
 * 不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。我们要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点。
 * 陷阱2
 * 样例中最小节点 可能是int的最小值，如果这样使用最小的int来比较也是不行的。
 * 此时可以初始化比较元素为longlong的最小值。
 *
 * @author Liyc
 * @date 2024/1/11 15:02
 **/

public class Solution18 {
    private TreeNode max;

    /**
     * 递归法
     * @param root
     * @return
     */
    public boolean isValidBST1(TreeNode root) {
        if (root == null) return true;
        //左
        boolean left = isValidBST1(root.left);
        if (!left) {
            return false;
        }
        //中
        if (max != null && max.val >= root.val) {
            return false;
        }
        max = root;
        //右
        boolean right = isValidBST1(root.right);
        return right;
    }

    /**
     * 迭代法
     * @param root
     * @return
     */
    public boolean isValidBST2(TreeNode root) {
        if (root == null) return true;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;//左
            }
            TreeNode node = stack.pop();
            if (pre != null && pre.val >= node.val) {
                return false;
            }
            pre = node;

            root = node.right;//右
        }
        return true;
    }
}
